///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
*	Contains source code from the article "Radix Sort Revisited".
*	\file		LaborRevisitedRadix.h
*	\author		Pierre Terdiman
*	\date		April, 4, 2000
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Include Guard
#ifndef __LABORRADIXSORT_H__
#define __LABORRADIXSORT_H__
#include "LaborCoreDef.h"
NAMESPACE_LABOR3D_BEGIN
//! Allocate histograms & offsets locally
#define RADIX_LOCAL_RAM

enum ELRadixHint
{
	RADIX_SIGNED,		//!< Input values are signed
	RADIX_UNSIGNED,		//!< Input values are unsigned

	RADIX_FORCE_DWORD = 0x7fffffff
};

class  LABORCORE_API CLRadixSort
{
public:
	// Constructor/Destructor
	CLRadixSort();
	~CLRadixSort();
	// Sorting methods
	CLRadixSort&		sort(const unsigned int* input, unsigned int nb, ELRadixHint hint=RADIX_SIGNED);
	CLRadixSort&		sort(const float* input, unsigned int nb);

	//! Access to results. mRanks is a list of indices in sorted order, i.e. in the order you may further process your data
	inline	const unsigned int*		getRanks()			const	{ return mRanks;		}

	//! mIndices2 gets trashed on calling the sort routine, but otherwise you can recycle it the way you want.
	inline	unsigned int*			getRecyclable()		const	{ return mRanks2;		}

	// Stats
	unsigned int			getUsedRam()		const;
	//! Returns the total number of calls to the radix sorter.
	inline	unsigned int			getNbTotalCalls()	const	{ return mTotalCalls;	}
	//! Returns the number of eraly exits due to temporal coherence.
	inline	unsigned int			getNbHits()			const	{ return mNbHits;		}

private:
#ifndef RADIX_LOCAL_RAM
	unsigned int*			mHistogram;			//!< Counters for each unsigned char
	unsigned int*			mOffset;			//!< Offsets (nearly a cumulative distribution function)
#endif
	unsigned int			mCurrentSize;		//!< Current size of the indices list
	unsigned int*			mRanks;				//!< Two lists, swapped each pass
	unsigned int*			mRanks2;
	// Stats
	unsigned int			mTotalCalls;		//!< Total number of calls to the sort routine
	unsigned int			mNbHits;			//!< Number of early exits due to coherence
	// Internal methods
	void			checkResize(unsigned int nb);
	bool			resize(unsigned int nb);
};

NAMESPACE_LABOR3D_END

#endif // __LABORRADIXSORT_H__
